package developer.算法.二分查找.寻找旋转排序数组中的最小值;

/**
 * @author zhangyongkang
 * @time 2025/4/2 17:00
 * @description 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
 * 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
 * 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
 * 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
 * <p>
 * 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
 * <p>
 * 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [3,4,5,1,2]
 * 输出：1
 * 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
 * 示例 2：
 * <p>
 * 输入：nums = [4,5,6,7,0,1,2]
 * 输出：0
 * 解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
 * 示例 3：
 * <p>
 * 输入：nums = [11,13,15,17]
 * 输出：11
 * 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
 * <p>
 * n == nums.length
 * 1 <= n <= 5000
 * -5000 <= nums[i] <= 5000
 */
public class Calc {

    public static void main(String[] args) {
        Solution4 solution = new Solution4();
        System.out.println(solution.findMin(new int[]{4, 5, 6, 7, 0, 1, 2}));
        System.out.println(solution.findMin(new int[]{3, 4, 5, 1, 2}));
    }

    static class Solution4 {
        public int findMin(int[] nums) {
            boolean isInOrder = false;
            int min = Integer.MAX_VALUE;
            int left = 0, right = nums.length - 1;

            while (left < right) {
                int midIdx = left + (right - left) / 2;
                int midVal = nums[midIdx];
                if (nums[left] <= midVal && nums[right] >= midVal) {//不在顺序区间
                    min = Math.min(min, nums[left]);
                    right = midIdx - 1;
                } else {
                    min = Math.min(min, midVal);
                    left = midIdx + 1;
                }

            }
            return min;
        }
    }


    static class Solution3 {
        public int findMin(int[] nums) {
            //判定当前的中间的点是否在最小的区间  也就是  左边比我小  右边比我大
            int left = 0, right = nums.length - 1;
            int min = Integer.MAX_VALUE;
            while (left < right) {
                int midIdx = left + (right - left) / 2;//中间位置的索引
                int midVal = nums[midIdx];
                if (nums[left] >= midVal || nums[right] <= midVal) {//说明此时是不在顺序区间的
                    min = Math.min(min, midVal);
                    left = midIdx + 1;
                } else {
                    min = Math.min(min, nums[left]);
                    right = midIdx - 1;
                }
            }
            return min;

        }
    }


    static class Solution {
        public int findMin(int[] nums) {
            int min = Integer.MAX_VALUE;

            int left = 0, right = nums.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;//中间索引
                int midVal = nums[mid];
                //如果左边小  右边大  就说明在顺序区间
                int leftVal = nums[left];
                if (leftVal <= midVal) {//如果左边处于区间
                    min = Math.min(min, leftVal);
                    left = mid + 1;
                } else {
                    min = Math.min(midVal, min);
                    right = mid - 1;
                }
            }
            return min;
        }
    }
}
